package offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class offer_0032_3 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new LinkedList<>();
        List<Integer> path=new LinkedList<>();
        Stack<TreeNode> stack1=new Stack<>();
        Stack<TreeNode> stack2=new Stack<>();
        if(root==null) return list;
        int count1=1;
        int count2=0;
        stack1.push(root);
        while(!stack1.isEmpty()){
            for(int i=0;i<count1;++i){
                TreeNode node=stack1.pop();
                if(node.left!=null){
                    stack2.push(node.left);
                    count2++;
                }
                if(node.right!=null){
                    stack2.push(node.right);
                    count2++;
                }
                path.add(node.val);
            }
            if(path.isEmpty()) break;
            list.add(new ArrayList<>(path));
            path.clear();
            count1=0;
            for(int i=0;i<count2;++i){
                TreeNode node=stack2.pop();
                if(node.right!=null){
                    stack1.push(node.right);
                    count1++;
                }
                if(node.left!=null){
                    stack1.push(node.left);
                    count1++;
                }
                path.add(node.val);
            }
            if(path.isEmpty()) break;
            list.add(new ArrayList<>(path));
            path.clear();
            count2=0;
        }
        return list;
    }
}
